class Solution {
public:
    vector<int> grayCode(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<int> result;
		vector<bool> visited(1 << n);

        result.push_back(0);
		visited[0] = true;
		int last = 0;
		for (int i = 1; i < (1 << n); ++i) {
			for (int j = 0; j < n; ++j) {
				int value = last ^ (1 << j);
				if (!visited[value]) {
					result.push_back(value);
					visited[value] = true;
					last = value;
					break;
				}
			}
		}

		return result;
    }
};